package org.demo.algorithm;
/**
 * 回溯法计算子集
 * @author  
 * @date    2010-9-14
 * @file    org.demo.algorithm.SubSet.java
 */
public class SubSet {
	private static String[] source;
	
	public static void main(String[] args) {
		source = new String[]{"A","B","C","D"};
		int[] data = new int[source.length];
		calcSubset(0,source.length,data);
		System.out.println("--ok.--");
	}
	/**
	 * 计算子集
	 * @param currentIndex 当前下标 0<= currentIndex <= max
	 * @param max          数组大小 max == data.length
	 * @param data         辅助数组：用 1，0来记录元素是否使用
	 */
	public static void calcSubset(int currentIndex,int max,int[] data){
		if (currentIndex >= max){
			output(data);
			return;
		}
		data[currentIndex] = 1;
		calcSubset(currentIndex+1,max,data);
		// 回溯
		data[currentIndex] = 0;
		calcSubset(currentIndex+1,max,data);
	}
	/**
	 * 输出
	 * @param data
	 */
	private static void output(int[] data){
		for (int i=0; i<data.length; i++){
			if (data[i] == 1){
				System.out.print(source[i]);
			}
		}
		System.out.println();
	} 
}
